/*
 * Copyright (c) 2009-2010 HIT Microelectronic Center
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met: redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer;
 * redistributions in binary form must reproduce the above copyright
 * notice, this list of conditions and the following disclaimer in the
 * documentation and/or other materials provided with the distribution;
 * neither the name of the copyright holders nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 *
 *
 * Authors: Gou Pengfei
 *          Jin Yinghan
 *
 * Date:    Dec. 2009
 *
 */

#ifndef __CPU_EDGE_INST_QUEUE_HH__
#define __CPU_EDGE_INST_QUEUE_HH__

#include <list>
#include <map>
#include <queue>
#include <deque>
#include <vector>

#include "base/statistics.hh"
#include "base/timebuf.hh"
#include "base/types.hh"
#include "cpu/inst_seq.hh"
#include "cpu/op_class.hh"
#include "sim/eventq.hh"
#include "cpu/edge/cpu.hh"
#include "cpu/edge/dep_graph.hh"

class DerivEdgeCPUParams;
class FUPool;

/**
 * This is a IQ working in data flow execution style.
 */
template <class Impl>
class InstructionQueue
{
  public:
    //Typedefs from the Impl.
    typedef typename Impl::CPU CPU;
    typedef typename Impl::DynInstPtr DynInstPtr;
    typedef typename Impl::EdgeBlockPtr EdgeBlockPtr;
    typedef typename Impl::CPUPol::Execute Execute;
    typedef typename Impl::CPUPol::MemDepUnit MemDepUnit;
    typedef typename Impl::CPUPol::Issue2Execute Issue2Execute;
    typedef typename Impl::CPUPol::TimeStruct TimeStruct;

    typedef typename std::vector<DynInstPtr>::iterator QueueIt;

    // Typedef of ISA specific types.
    typedef TheISA::BlockID BlockID;
    typedef TheISA::InstID InstID;
    typedef TheISA::ConsumerID ConsumerID;
    typedef TheISA::ConsumerType ConsumerType;
    typedef TheISA::ConsumerSubType ConsumerSubType;

    typedef TheISA::OpSize OpSize;

    friend class Impl::CPU;

    /** FU completion event class. */
    class FUCompletion : public Event {
      private:
        /** Executing instruction. */
        DynInstPtr inst;

        /** Index of the FU used for executing. */
        int fuIdx;

        /** Pointer back to the instruction queue. */
        InstructionQueue<Impl> *iqPtr;

        /** Should the FU be added to the list to be freed upon
         * completing this event.
         */
        bool freeFU;

      public:
        /** Construct a FU completion event. */
        FUCompletion(DynInstPtr &_inst, int fu_idx,
                     InstructionQueue<Impl> *iq_ptr);

        virtual void process();
        virtual const char *description() const;
        void setFreeFU() { freeFU = true; }
    };

    /** Constructs an IQ. */
    InstructionQueue(CPU *cpu_ptr, Execute* execute, DerivEdgeCPUParams *params);

    /** Destructs the IQ. */
    ~InstructionQueue();

    /** Returns the name of the IQ. */
    std::string name() const;

    /** Registers statistics. */
    void regStats();

    /** Resets all instruction queue state. */
    void resetState();

    /** Sets active threads list. */
    void setActiveThreads(std::list<ThreadID> *at_ptr);

    /** Sets the timer buffer between issue and execute. */
    void setIssueToExecuteQueue(TimeBuffer<Issue2Execute> *i2eQueue);

    /** Sets the global time buffer. */
    void setTimeBuffer(TimeBuffer<TimeStruct> *tb_ptr);

    /** Switches out the instruction queue. */
    void switchOut();

    /** Takes over execution from another CPU's thread. */
    void takeOverFrom();

    /** Returns if the IQ is switched out. */
    bool isSwitchedOut() { return switchedOut; }

    /** Number of entries needed for given amount of threads. */
    int entryAmount(ThreadID num_threads);

    /** Resets max entries for all threads. */
    void resetEntries();

    /** Returns total number of free entries. */
    unsigned numFreeEntries();

    /** Returns number of free entries for a thread. */
    unsigned numFreeEntries(ThreadID tid);

    /** Returns whether or not the IQ is full. */
    bool isFull();

    /** Returns whether or not the IQ is full for a specific thread. */
    bool isFull(ThreadID tid);

    /** Returns if there are any ready instructions in the IQ. */
    bool hasReadyInsts();

    /** Returns the LSID of the last fetched store. */
    TheISA::LsID getLastFetchedStore(){return lastFetchedStore;}

    /** Inserts a new instruction into the IQ. */
    void insert(DynInstPtr &new_inst, int position);

    /** Builds mem inst dependent. */
    void buildMemDependent( DynInstPtr &mem_inst);

    /** Inserts a new, non-speculative instruction into the IQ. */
    void insertNonSpec(DynInstPtr &new_inst);

    /** Inserts a memory or write barrier into the IQ to make sure
     *  loads and stores are ordered properly.
     */
    void insertBarrier(DynInstPtr &barr_inst);

    /** Returns the oldest scheduled instruction, and removes it from
     * the list of instructions waiting to execute.
     */
    DynInstPtr getInstToExecute();

    /**
     * Records the instruction as the producer of a register without
     * adding it to the rest of the IQ.
     * @todo: Delete this method due to its unability of supporting data flow
     * execution.
     */
    void recordProducer(DynInstPtr &inst) {addToProducers(inst);}

    /** Process FU completion event. */
    void processFUCompletion(DynInstPtr &inst, int fu_idx);

    /**
     * Schedules ready instructions, adding the ready ones (oldest first) to
     * the queue to execute.
     */
    void scheduleReadyInsts();

    /** Schedules a single specific non-speculative instruction. */
    void scheduleNonSpec(const InstSeqNum &inst);

    /**
     * Commits all instructions up to and including the given sequence number,
     * for a specific thread and a specific block.
     */
    void commit(const TheISA::BlockID &commit_bid, ThreadID tid = 0);

    /**
     * Write back register write instructions in one specific inst block for a specific
     * thread.
     */
    void writeBack(TheISA::BlockID wb_block_id, ThreadID tid = 0);

    /**
     * Mark instructions belongs to a specific inst block as block-completed.
    */
    void complete(EdgeBlockPtr & inst_block);

    /** Complete reg-write inst in reg dep graph. */
    void completeInRegDepGraph(DynInstPtr &inst);

    /** Wakes all dependents of a completed instruction.
     *  This is handled in a data flow execution style.
    */
    int wakeDependents(DynInstPtr &completed_inst);

    /** Adds a ready memory instruction to the ready list. */
    void addReadyMemInst(DynInstPtr &ready_inst);

    /**
     * Reschedules a memory instruction. It will be ready to issue once
     * replayMemInst() is called.
     */
    void rescheduleMemInst(DynInstPtr &resched_inst);

    /** Replays a memory instruction. It must be rescheduled first.
     *   @todo: Figure out if this method should be reserved or not.
    */
    void replayMemInst(ThreadID tid);

        /** Moves an instruction to the ready queue if it is ready. */
    void addIfReady(DynInstPtr &inst);

    /** Completes a memory operation. */
    void completeMemInst(DynInstPtr &completed_inst);

    /** Indicates an ordering violation between a store and a load. */
    void violation(DynInstPtr &store, DynInstPtr &faulting_load);

    /**
     * Squashes instructions for a thread. Squashing information is obtained
     * from the time buffer.
     */
    void squash(ThreadID tid);

    /** Returns the number of used entries for a thread. */
    unsigned getCount(ThreadID tid) { return count[tid]; };

    /** Debug function to print all instructions. */
    void printInsts();

  private:
    /** Does the actual squashing. */
    void doSquash(ThreadID tid);

    /////////////////////////
    // Various pointers
    /////////////////////////

    /** Pointer to the CPU. */
    CPU *cpu;

    /**Pointer to Execute stage.*/
    Execute *executeStage;

    /** The memory dependence unit, which tracks/predicts memory dependences
     *  between instructions.
     */
    MemDepUnit memDepUnit[Impl::MaxThreads];

    /** The queue to the execute stage.  Issued instructions will be written
     *  into it.
     */
    TimeBuffer<Issue2Execute> *issueToExecuteQueue;

    /** The backwards time buffer. */
    TimeBuffer<TimeStruct> *timeBuffer;

    /** Wire to read information from timebuffer. */
    typename TimeBuffer<TimeStruct>::wire fromCommit;

    /** Function unit pool. */
    FUPool *fuPool;

    //////////////////////////////////////
    // Instruction queues, ready queues, and ordering
    //////////////////////////////////////

    /** Container of all the instructions in the IQ (some of which may be issued). */
    std::vector<DynInstPtr> instQueue[Impl::MaxThreads][Impl::MaxFrameNum];
    std::vector<DynInstPtr> readQueue[Impl::MaxThreads][Impl::MaxFrameNum];
    std::vector<DynInstPtr> writeQueue[Impl::MaxThreads][Impl::MaxFrameNum];

    /** This array will record which block belongs to a specific
     * frame. 0 means this frame is not used right now. */
    uint64_t frameRecordBoard[Impl::MaxThreads][Impl::MaxFrameNum];

    /** List of instructions that are ready to be executed. */
    std::list<DynInstPtr> instsToExecute;

    /**
     * Struct for comparing entries to be added to the priority queue.
     * This gives reverse ordering to the instructions in terms of
     * sequence numbers: the instructions with smaller sequence
     * numbers (and hence are older) will be at the top of the
     * priority queue.
     */
    struct pqCompare {
        bool operator() (const DynInstPtr &lhs, const DynInstPtr &rhs) const
        {
            return lhs->seqNum > rhs->seqNum;
        }
    };

    typedef std::priority_queue<DynInstPtr, std::vector<DynInstPtr>, pqCompare>
    ReadyInstQueue;

    /** List of ready instructions, per op class.  They are separated by op
     *  class to allow for easy mapping to FUs.
     */
    ReadyInstQueue readyInsts[Num_OpClasses];

    /** List of non-speculative instructions that will be scheduled
     *  once the IQ gets a signal from commit.  While it's redundant to
     *  have the key be a part of the value (the sequence number is stored
     *  inside of DynInst), when these instructions are woken up only
     *  the sequence number will be available.  Thus it is most efficient to be
     *  able to search by the sequence number alone.
     * @todo: Figure out if we really need this.
     */
    std::map<InstSeqNum, DynInstPtr> nonSpecInsts;

    typedef typename std::map<InstSeqNum, DynInstPtr>::iterator NonSpecMapIt;

    /** Entry for the list age ordering by op class. */
    struct ListOrderEntry {
        OpClass queueType;
        InstSeqNum oldestInst;
    };

    /** List that contains the age order of the oldest instruction of each
     *  ready queue.  Used to select the oldest instruction available
     *  among op classes.
     *  @todo: Might be better to just move these entries around instead
     *  of creating new ones every time the position changes due to an
     *  instruction issuing.  Not sure std::list supports this.
     */
    std::list<ListOrderEntry> listOrder;

    typedef typename std::list<ListOrderEntry>::iterator ListOrderIt;

    /** Tracks if each ready queue is on the age order list. */
    bool queueOnList[Num_OpClasses];

    /** Iterators of each ready queue.  Points to their spot in the age order
     *  list.
     */
    ListOrderIt readyIt[Num_OpClasses];

    /** Add an op class to the age order list. */
    void addToOrderList(OpClass op_class);

    /**
     * Called when the oldest instruction has been removed from a ready queue;
     * this places that ready queue into the proper spot in the age order list.
     */
    void moveToYoungerInst(ListOrderIt age_order_it);

    /** Register dependence graph to maintain register forwarding between
     *   inst blocks.
     */
     DependencyGraph<DynInstPtr> regDepGraph;

    //////////////////////////////////////
    // Various parameters
    //////////////////////////////////////

    /** IQ Resource Sharing Policy */
    enum IQPolicy {
        Dynamic,
        Partitioned,
        Threshold
    };

    /** IQ sharing policy for SMT. */
    IQPolicy iqPolicy;

    /** Number of Total Threads*/
    ThreadID numThreads;

    /** Pointer to list of active threads. */
    std::list<ThreadID> *activeThreads;

    /** Per Thread IQ count */
    unsigned count[Impl::MaxThreads];

    /** Max IQ Entries Per Thread */
    unsigned maxEntries[Impl::MaxThreads];

    /** Number of free IQ entries left. */
    unsigned freeEntries;

    /** The number of entries in the instruction queue. */
    unsigned numEntries;

    /** The total number of instructions that can be issued in one cycle. */
    unsigned totalWidth;

    /** The number of physical registers in the CPU. */
    unsigned numPhysRegs;

    /** The number of physical integer registers in the CPU. */
    unsigned numPhysIntRegs;

    /** The number of floating point registers in the CPU. */
    unsigned numPhysFloatRegs;

    /** Delay between commit stage and the IQ.
     *  @todo: Make there be a distinction between the delays within execution.
     */
    unsigned commitToExecuteDelay;

    /** Is the IQ switched out. */
    bool switchedOut;

    /** Last fetch store will be marked using the LSID. */
    TheISA::LsID lastFetchedStore;

    /** The sequence number of the squashed instruction. */
    InstSeqNum squashedSeqNum[Impl::MaxThreads];

    /** A cache of the recently woken registers.  It is 1 if the register
     *  has been woken up recently, and 0 if the register has been added
     *  to the dependency graph and has not yet received its value.
     *  In EDGE model, register will be modified by special register read/write
     *  insts. This will happen when inst blocks start executing (for read)
     *  or end executing( for write). Scoreboard will mark the register as
     *  ready or not after inst blocks committed.
     */
    std::vector<bool> regScoreboard;

    /** If we get a perfect predication? */
    bool isPerfectPredication;

    /** Adds an instruction to the dependency graph, as a consumer.
     *  @todo: Is this neccesary?
     */
    bool addToDependents(DynInstPtr &new_inst);

    /** Adds an instruction to the dependency graph, as a producer.
     *  @todo: Is this neccesary?
     */
    void addToProducers(DynInstPtr &new_inst);

    /** Debugging function to count how many entries are in the IQ.  It does
     *  a linear walk through the instructions, so do not call this function
     *  during normal execution.
     */
    int countInsts();

    /** Debugging function to dump all the list sizes, as well as print
     *  out the list of nonspeculative instructions.  Should not be used
     *  in any other capacity, but it has no harmful sideaffects.
     */
    void dumpLists();

    /** Debugging function to dump out all instructions that are in the
     *  IQ.
     */
    void dumpInsts();

    /** Stat for number of instructions added. */
    Stats::Scalar iqInstsAdded;
    Stats::Scalar iqReadsAdded;
    Stats::Scalar iqWritesAdded;

    Stats::Scalar iqInstsIssued;
    Stats::Scalar iqIntInstsIssued;
    /** Stat for number of floating point instructions issued. */
    Stats::Scalar iqFloatInstsIssued;
    /** Stat for number of branch instructions issued. */
    Stats::Scalar iqBranchInstsIssued;
    /** Stat for number of memory instructions issued. */
    Stats::Scalar iqMemInstsIssued;
    /** Stat for number of miscellaneous instructions issued. */
    Stats::Scalar iqMiscInstsIssued;
    /** Stat for number of squashed instructions that were ready to issue. */
    Stats::Scalar iqDummyInstsIssued;
    /** Stat for number of squashed instructions examined when squashing. */
    Stats::Scalar iqInstsSquashed;
    /** Stat for number of reg-reads dependent upon unexecuted reg-writes. */
    Stats::Scalar iqRegReadDep;
    /** Stat for number of reg-writes writed back. */
    Stats::Scalar iqRegWriteWrited;
    /** Stat for number of operands propagated. */
    Stats::Scalar iqOperandsPropagated;
    /** Stat for number of nullified token propagated. */
    Stats::Scalar iqNullTokenPropagated;
    /** Stat for number of exeception token propagated. */
    Stats::Scalar iqExceptTokenPropagated;
    /** Stat for number of predication propagated. */
    Stats::Scalar iqPredicationPropagated;
    /** Stat for number of correctly predict predication. */
    Stats::Scalar iqCorrectPredPredication;

    // Also include number of instructions rescheduled and replayed.

    /** Distribution of the number of instructions issued. */
    Stats::Distribution numIssuedDist;

    /** Number of times an instruction could not be issued because a
     * FU was busy.
     */
    Stats::Vector statFuBusy;

    /** Stat for total number issued for each instruction type. */
    Stats::Vector2d statIssuedInstType;

    /** Number of instructions issued per cycle. */
    Stats::Formula issueRate;

    /** Number of times the FU was busy. */
    Stats::Vector fuBusy;
    /** Number of times the FU was busy per instruction issued. */
    Stats::Formula fuBusyRate;
};

#endif //__CPU_EDGE_INST_QUEUE_HH__
